home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / docs / corsoguide / liste-6.txt < prev    next >
Text File  |  1992-09-03  |  7KB  |  162 lines
  1. Liste e nodi
  2.  
  3. Il sistema operativo mantiene durante il suo periodo di attività un elevato
  4. numero di liste di dati di vario tipo: schermi, finestre, blocchi memoria,
  5. task, interrupt ecc. Dato che tutte queste liste hanno un numero di elementi
  6. variabile, vengono realizzate mediante strutture linkate; ciò significa che
  7. oltre ai dati di un elemento della lista viene inserito un indirizzo che
  8. costituisce il puntatore al prossimo elemento in modo da costituire una
  9. catena. Exec provvede fornendo un implementazione standard per tutte le
  10. liste che gestisce, mettendo a disposizione quindi le routine per ricerca,
  11. inserimento e altre che non gravano così sul programmatore; la struttura
  12. linkata realizzata con exec viene denominata coda (in inglese queue)
  13. bidirezionale, cioè ogni elemento oltre ad avere il puntatore all'elemento
  14. successivo ha anche il puntatore a quello precedente; in più vi sono due
  15. elementi particolari, Head node e Tail node che puntano rispettivamente al
  16. primo e all'ultimo elemento della lista e necessitano per iniziare una
  17. qualsiasi procedura di ricerca. In termini pratici tutto ciò viene tradotto
  18. tramite una struttura:
  19.  
  20. struct Node
  21. {
  22.   struct Node *ln_Succ;
  23.   struct
  24.   Node *ln_Prec;
  25.   UBYTE ln_Type;
  26.   BYTE ln_Pri;
  27.   char *ln_Name;
  28. };
  29.  
  30. Come vedete la struttura Node non solo è costituita dai puntatori al
  31. nodo successivo e precedente ma anche da altri dati: 'ln_Type' indica il
  32. tipo del nodo ed assume diverse definizioni a seconda dell'ambiente in cui
  33. viene utilizzato che specificheremo volta per volta; 'ln_Pri' indica la
  34. priorità dell'elemento (nella lista di task indica chi ha la precedenza
  35. sugli altri) e per questo molte volte influisce sull'ordinamento della
  36. lista (vale a dire viene prima l'elemento con priorità più alta) di solito
  37. 'ln_Pri' assume 0; 'ln_Name' è il puntatore ad una stringa che identifica
  38. univocamente l'elemento e può essere utilizzato per la ricerca; questi tre
  39. elementi sono opzionali e vedremo volta per volta quando vengono
  40. utilizzati. Questa struttura deve essere definita all'inizio dell'elemento
  41. dati della lista; ad esempio:
  42.  
  43. struct Persona
  44. {
  45.   struct Node LinkNode;
  46.   char *Nome;
  47.   char *Cognome;
  48.   int anni;
  49.   char *codicefis;
  50. };
  51.  
  52. E' possibile comunque utilizzare una struttura "minima" e cioè senza
  53. ln_Type, ln_Pri, ln_Name nella quale non fossero necessarie, denominata
  54. MinNode:
  55.  
  56. struct MinNode
  57. {
  58.   struct MinNode *min_Succ;
  59.   struct MinNode *min_Pred;
  60. };
  61.  
  62. Occorre mantenere anche le informazioni riguardanti l'indirizzo del nodo
  63. di testa e di quello di coda, per cui si utilizzerà la struttura List:
  64.  
  65. struct List
  66. {
  67.   struct Node *lh_Head;
  68.   struct Node *lh_Tail;
  69.   struct Node *lh_TailPred;
  70.   UBYTE lh_Type;
  71.   UBYTE lh_Pad;
  72. };
  73.  
  74. lh_Type è un codice numerico che indica il tipo di lista (o meglio qual è
  75. il contenuto di codesta); lh_Pad non contiene alcun informazione e serve
  76. solamente ad assicurare l'allineamento a word di dati eventualmente presenti
  77. dopo; i primi tre valori sono puntatori a nodi e rappresentano la testa e la
  78. coda della lista; tale modo di conservare i puntatori non è quello
  79. convenzionale in quanto normalmente, si considerano i puntatori agli
  80. elementi di testa e di coda e si devono gestire una serie di casi
  81. particolari (inserimento in testa, inserimento in una lista vuota ecc.)
  82. implementando così una serie di verifiche di sicurezza; in questa struttura
  83. invece sono direttamente presenti gli elementi di testa e di coda da
  84. considerare "immaginari" perché non contengono alcun dato; in termini
  85. pratici lh_Head ed lh_Tail rappresentano rispettivamente il puntatore
  86. all'elemento successivo e all'elemento precedente di questo nodo di testa
  87. immaginario, ed il primo è il puntatore al primo nodo effettivo della
  88. struttura dati, ed il secondo vale 0; mentre lh_Tail e lh_TailPred
  89. costituiscono il successivo e il precedente del nodo di coda immaginario e
  90. valgono 0 per il primo e l'indirizzo dell'ultimo nodo effettivo per il
  91. secondo (lh_Tail è condiviso perché vale sempre 0); capite che facendo così
  92. si eliminano tutti i casi particolari e con essi le verifiche necessarie per
  93. implementarli; infatti in caso di lista vuota esistono comunque due elementi
  94. (la testa e la coda immaginari), per cui l'inserimento in una lista vuota è
  95. uguale all'inserimento normale, oppure l'inserimento di un nodo in testa
  96. alla lista equivale realmente ad un inserimento qualunque, poiché il nodo di
  97. testa della lista si trova sempre dopo quello immaginario è quindi non è
  98. realmente in testa anche se al programmatore sembra che sia così.
  99. Dopo questa spiegazione da cane che si morde la coda, per inizializzare una
  100. lista e gestirla vi sono comunque delle funzioni di exec apposite e che
  101. quindi non richiedono nessuna operazione aggiuntiva da parte del
  102. programmatore.
  103.  
  104. struct MinList
  105. {
  106.   struct MinNode *mlh_Head;
  107.   struct MinNode *mlh_Tail;
  108.   struct MinNode *mlh_TailPred;
  109. };
  110.  
  111. questa struttura viene utilizzata nella stessa maniera di List salvo che per
  112. questa non vanno specificate le informazioni aggiuntive. Osserviamo ora le
  113. funzioni messe a disposizione da Exec per la gestione delle liste:
  114.  
  115. NewList(Lista);
  116.  
  117. dove Lista è il puntatore ad una struttura List; NewList effettua
  118. l'inizializzazione della lista vuota ed imposta correttamente i valori di
  119. Lista.
  120.  
  121. AddHead(Lista,Nodo);
  122. AddTail(Lista,Nodo);
  123. Enqueue(Lista,Nodo);
  124.  
  125. dove Lista è sempre il puntatore ad una struttura List (se è appena creata
  126. occorre inizializzarla con NewList) e Nodo è il puntatore alla struttura
  127. Node da inserire nella lista; AddHead serve per inserire il nodo in testa
  128. alla lista, AddTail per inserirlo in fondo ed Enqueue per inserire il nodo
  129. in modo da mantenere la lista ordinata per priorità (ln_Pri); tenete
  130. presente che Enqueue deve operare su una lista già ordinata (vale a dire
  131. ogni elemento della lista deve essere stato inserito con questa funzione,
  132. oppure facendo attenzione che la posizione a seconda della priorità sia
  133. giusta); con Enqueue, il nodo verrà inserito dopo l'ultimo elemento con
  134. priorità maggiore o uguale a quella sua ed inoltre, il primo elemento della
  135. lista (quello di testa) ha priorità maggiore (quindi ordinamento numerico
  136. decrescente); questa funzione non può essere utilizzata ovviamente con liste
  137. minime.
  138.  
  139. Insert(Lista,Nodo,NodoPrec);
  140.  
  141. dove Lista e Nodo hanno lo stesso significato di prima e NodoPrec è il
  142. puntatore ad un nodo della lista "Lista"; Insert inserirà il nodo "Nodo"
  143. nella lista "Lista" nella posizione immediatamente successiva a NodoPrec.
  144.  
  145. Remove(Nodo);
  146. Nodo = (struct Node *)RemHead(Lista);
  147. Nodo = (struct Node *)RemTail(Lista);
  148.  
  149. Remove rimuoverà il nodo "Nodo" dalla lista in cui è presente; quì non
  150. occorre specificare nessuna lista giacché in Nodo stesso sono presente tutte
  151. le informazioni per la sua eliminazione (puntatore al nodo precedente ad a
  152. quello successivo); RemHead e RemTail rimuovono rispettivamente il nodo di
  153. testa e quello di coda e ne ritornano l'indirizzo in caso serva (per la sua
  154. deallocazione o per altri usi).
  155.  
  156. Nodo = (struct Node *)FindName(Lista,nome);
  157.  
  158. dove nome è il puntatore ad una stringa; FindName ricercherà il nodo con
  159. nome (ln_Name) "nome" nella lista "Lista" e se lo troverà ritornerà il suo
  160. indirizzo altrimenti ritornerà NULL; questa funzione non può essere
  161. utilizzata con le liste minime.
  162.